package leetcode.editor.cn.dsa02_linkedlist;
//给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
// 如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
// 您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

public class AddTwoNumbers2_2 {

    //leetcode submit region begin(Prohibit modification and deletion)
    public class ListNode {
        int val; // 数据域
        ListNode next; // 指针域，指向下一个节点
        ListNode() {}
        ListNode(int val) { this.val = val; }
    }
    class Solution {
        /**
         * 暴力解法：存在的问题：使用long也会存在溢出
         * 解决办法： java.math.BigInteger
         * 该类在leetcode默认环境没有导⼊，所以使用全类名编写
         *
         * @param l1
         * @param l2
         * @return
         */
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            // 把链表转成数字
            java.math.BigInteger l1Value = java.math.BigInteger.valueOf(0);
            int digit = 0; // 位数
            while (l1 != null) {
                java.math.BigInteger carry =
                        java.math.BigInteger.valueOf(10).pow(digit);
                l1Value = l1Value.add(carry.multiply(java.math.BigInteger.valueOf(l1.val)));
                l1 = l1.next; // //链表指向下⼀个节点
                digit++;
            }
            java.math.BigInteger l2Value = java.math.BigInteger.valueOf(0);
            digit = 0;
            while (l2 != null) {
                java.math.BigInteger carry =
                        java.math.BigInteger.valueOf(10).pow(digit);
                l2Value = l2Value.add(carry.multiply(java.math.BigInteger.valueOf(l2.val)));
                l2 = l2.next;
                digit++;
            }
            ListNode head = new ListNode();
            ListNode cur = head;
            // 两数相加
            java.math.BigInteger sum = l1Value.add(l2Value);
            if (sum.compareTo(java.math.BigInteger.valueOf(0)) == 0) {
                head = new ListNode(0);
                return head;
            }
            // 数字再转成链表
            while (sum.compareTo(java.math.BigInteger.valueOf(0)) > 0) {
                int val = sum.mod(java.math.BigInteger.valueOf(10)).intValue();
                sum = sum.divide(java.math.BigInteger.valueOf(10));
                cur.next = new ListNode(val);
                cur = cur.next;
            }
            return head.next;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)
}